import java.util.ArrayList;
import java.util.List;

/*
 * @author zzr
 * @date: 2025/03/14  17:42
 * @description:杨辉三角
 */
public class Test3 {

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();

        //第一行
        List<Integer> row = new ArrayList<>();
        row.add(1);
        ret.add(row);

        for (int i = 1; i < numRows; i++) { //注意 i 这里的起始值为1，因为第一行已经有了curRow了

            List<Integer> curRow = new ArrayList<>();
            //第一个元素
            curRow.add(1);
            //中间列
            //杨辉中的每一行第一个和最后一个元素是1，中间的元素是上一行的两个元素之和
            //所以需要找到上一行
            List<Integer> prevRow = ret.get(i - 1);

            for (int j = 1; j < i; j++) {  //注意 j 这里的起始值为1 是因为第一个元素已经是1了
                int x = prevRow.get(j) + prevRow.get((j - 1));
                curRow.add(x);
            }
            //最后一个元素
            curRow.add(1);

            ret.add(curRow);
        }
        return ret;
    }
}
